// 不同的子序列 II
// 给定一个字符串 s，计算 s 的 不同非空子序列 的个数
// 因为结果可能很大，答案对 1000000007 取模
// 字符串的 子序列 是经由原字符串删除一些（也可能不删除）
// 字符但不改变剩余字符相对位置的一个新字符串
// 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是
// 测试链接 : https://leetcode.cn/problems/distinct-subsequences-ii/

#include <vector>
#include <string>

using namespace std;

class Code08_DistinctSubsequencesII
{
public:
    // 时间复杂度O(n)，n是字符串s的长度
    static int distinctSubseqII(string s)
    {
        const int mod = 1000000007;
        vector<int> cnt(26, 0);
        long long all = 1; // 使用 long long 以防溢出
        long long newAdd;

        for (char x : s)
        {
            newAdd = (all - cnt[x - 'a'] + mod) % mod;    // 最新增加的子序列数
            cnt[x - 'a'] = (cnt[x - 'a'] + newAdd) % mod; // 更新当前字符的子序列个数
            all = (all + newAdd) % mod;                   // 更新总的子序列个数
        }

        return (all - 1 + mod) % mod; // 减去空子序列
    }
};

#include <iostream>

int main()
{
    string s = "abc";
    int result = Code08_DistinctSubsequencesII::distinctSubseqII(s);

    // 输出结果
    cout << "The number of distinct subsequences II is: " << result << endl;

    return 0;
}
